package day0401;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;


public class Node28 {
    /**
     * 28.二叉树中序遍历输出 (输入不会做)
     * 示例：
     * 输入：a{b{d, e{g,h{,I}}},c{f}｝
     * 输出：dbgehiafc
     */

    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        String s = sc.nextLine();
//        int nodeNum = 0;
//        ArrayList<TreeNode> list = new ArrayList<>();
//        for (int i = 0; i < s.length(); i++) {
//            if (('a' < s.charAt(i) && s.charAt(i) < 'z') || ('A' < s.charAt(i) && s.charAt(i) < 'Z')) {
//                nodeNum++;
//                TreeNode treeNode = new TreeNode(s.charAt(i));
//                list.add(treeNode);
//            }
//        }
//        for (int i = 1; i < s.length(); i++) {
//            if (s.charAt(i) == '{' && s.charAt(i + 1) != ',') {
//                list.get(i - 1).left = list.get(i + 1);
//            }
//            if (s.charAt(i) == '{' && s.charAt(i + 1) == ',') {
//                list.get(i - 1).right = list.get(i + 1);
//            }
//            if (s.charAt(i) == '{' && s.charAt(i + 1) == ',') {
//                list.get(i - 1).right = list.get(i + 1);
//            }
//
//
//        }
        //todo 构造二叉树
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        t1.left = null;
        t1.right = t2;
        t2.left = t3;
        t2.right = null;
        List<Integer> list = inorderTraversal(t1);


    }

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root != null) {
            stack.push(root);
        }
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();//访问栈顶元素
            if (node != null) {
                if (node.right != null) {
                    stack.push(node.right);//添加右节点
                }
                stack.push(node);//添加中节点
                stack.push(null);//中节点访问过，但是还没有处理，加入空节点作为标记
                if (node.left != null) {
                    stack.push(node.left);//添加左节点
                }
            } else {// 只有遇到空节点的时候，才将下⼀个节点放进结果集
                node = stack.pop();//重新取出栈中元素
                ans.add(node.val);
            }
        }
        return ans;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
